package com.yun;

/**
 * Created by lsy
 * on 2020/7/16 18:14.
 * 八皇后排列方式计算
 */
public class TheEightQueue {
    public static int QUEUE_NUM = 10;
    // 12   311228500           递归346141200
    // 14  5515574300
    // 15 31249743600
    // 16 230468809400

    public static void main(String[] args) {
        TheEightQueue theEightQueue = new TheEightQueue();
        long l = System.nanoTime();
        theEightQueue.placeQueue(0);
        System.out.println(theEightQueue.size);
        System.out.println("cost time :" + (System.nanoTime() - l));
    }

    private int[] cols = new int[QUEUE_NUM]; // 记录每一行八皇后放置的位置
    private int size = 0;

    // 放置第n个皇后
    public void placeQueue(int n) {
        // 遍历已放置皇后，标记已放置的位置
        // 首行皇后直接放置
        boolean[] rows = new boolean[QUEUE_NUM]; // 判断此行的位置能不能防止，竖线，对角，斜对角有皇后无法防止。每次新一行防止都要重新计算
        for (int i = 0; i < n; i++) {
            rows[cols[i]] = true;
            if (cols[i] - (n - i) >= 0) {  // (n-i)见下表
                rows[cols[i] -(n -i)] = true;
            }
            if (cols[i] + n - i < QUEUE_NUM) {
                rows[cols[i] + n -i] = true;
            }
            // 你自己这么懒的吗？
            // 没有好的脑子，会不会用手画一画，罚你列出一种八皇后的情况，以儆效尤
        }
        for (int i = 0; i < QUEUE_NUM; i++) {
            // 判断位置是否可以放置
            if (rows[i]) {
                continue;
            }
            cols[n] = i;
            if (n < QUEUE_NUM - 1) {
//                rows[i] = true; 这里是错的！！！应该设置当前皇后所在列数
                placeQueue(n + 1);
            } else {
                // 放置最后一个
                size++;
//                printQueues(cols);
            }
        }
    }

    private void printQueues(int[] cols) {
        int n = cols.length;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (cols[i] == j) {
                    System.out.print("*");
                }else{
                    System.out.print("+");
                }
            }
            System.out.println();
        }
        System.out.println("--");
    }

    /**
     * 列出一种八皇后情况
     * 展示每行进入时，判断rows 哪里不可以放，
     */
//    第n行进入   rows情况 0    1      2     3    4     5      6     7      8             放置位置     判断位置1     判断位置2
//    0                  false,false,false,false,false,false,false,false,false,             0
//    1                  true, true, false,false,false,false,false,false,false,             2
//    2                  true, true, true, true, false,false,false,false,false,             4
//    3
//    4
//    5
//    6
//    7
//
//
//      *|
//    * *|*
//  * * *| * * // (n - i) 等腰直角三角形两个斜边相等，所以（n-i）就可以代表第i行映射到第n行需要的左右长度的一根棍子
// ——————           //  n代表循环的重点，i代表当前遍历的第几行，最大是n-1行。

}
